package com.atwulidun.recursion;

public class ArrangementAndCombination {
    public static void main(String[] args) {
        int[] arr1 = { 1, 2, 3, 4 };
        int[] arr2 = new int[3];// arr2是可以反复利用的，每次只存两个数
//        arrangement(arr1, arr2, 0, 0);
        fullArrangement(arr1, 0);
//        combination(arr1, arr2, 0 , 0);
//        repeatableCombination(arr1, arr2, 0 , 0);
    }

    // 最通用的排列

    /**
     *
     * @param arr1
     * 存储的是排列时可供存储的数字
     * @param arr2
     * 存储的是每一次排列好的数字，arr2.length <= arr1.length，且arr2可以循环被利用
     * @param start
     * 从arr1的start位开始取值赋给arr2
     * @param index
     * 指arr2的第index位
     */
    public static void arrangement(int[] arr1, int[] arr2, int start, int index) {
        // 若此时递归调用满足下面的条件，说明上一次调用完后arr2已经存满了数据，将arr2的内容打印出来，return结束即可
        if (index == arr2.length) {
            for (int i : arr2) {
                System.out.print(i);
            }
            System.out.println();
            return;
        }
        for (int i = start; i < arr1.length; ++i) {
            arr2[index] = arr1[i];// 假设i==3
            swap(arr1, start, i);// 3 1 2 4，下面的递归调用即是从1 2 4中再选一个数给arr2[index + 1]赋值，而1是第start + 1位
            arrangement(arr1, arr2, start + 1, index + 1);// 这里的start和index两个参数的值始终都是保持相等的
            swap(arr1, start, i);// 记得把3 1 2 4换回1 2 3 4，以便不影响i == 4时的操作
        }
    }

    // 全排列(可以对原来的数组直接进行修改，每一次递归调用后都将调用前对数组的修改进行复原，相当于多次利用原数组)
    public static void fullArrangement(int[] arr, int start) {
        if (start == arr.length - 1) {// 这里递归的结束条件写成start == arr.length效果也是一样的
            for (int i : arr) {
                System.out.print(i);
            }
            System.out.println();
            return;
        }
        for (int i = start; i < arr.length; ++i) {
            swap(arr, i ,start);
            fullArrangement(arr, start + 1);
            swap(arr, i , start);
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 组合
    public static void combination(int[] arr1, int[] arr2, int start, int index) {
        if (index == arr2.length) {
            for (int i : arr2) {
                System.out.print(i);
            }
            System.out.println();
            return;
        }
        for (int i = start; i < arr1.length; ++i) {
            arr2[index] = arr1[i];
//            combination(arr1, arr2 , start + 1, index + 1);// 注意：如果这里为start + 1，则会出错
            combination(arr1, arr2 , i + 1, index + 1);// arr2[index + 1]的值只能从当前i的下一位开始取，不然会重复
        }
    }
    // 可以有重复数字的组合
    public static void repeatableCombination(int[] arr1, int[] arr2, int start, int index) {
        if (index == arr2.length) {
            for (int i : arr2) {
                System.out.print(i);
            }
            System.out.println();
            return;
        }
        for (int i = start; i < arr1.length; ++i) {
            arr2[index] = arr1[i];
            // 每一次都是在arr1的所有数字中进行选择，故start始终都是不变的
            repeatableCombination(arr1, arr2 , start, index + 1);// 特别注意递归调用的是本函数，名字不要写错了！！！！！
        }
    }
}
